package com.example.leetcode;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-06-30
 * Time: 20:31
 */
public class Code_longestPalindromeSubseq {
    class Solution {
        public int longestPalindromeSubseq(String str) {
            int n = str.length();
            //以i位置元素为开头并且以j位置元素为结尾的最长回文子序列长度为dp[i][j]
            int[][] dp = new int[n][n];
            char[] s = str.toCharArray();
            //i <=j
            //s[i] != s[j]
            //      dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
            //s[i] == s[j]
            //      i==j dp[i][j] = 1
            //      i+1 == j  dp[i][j] = 2
            //      i < j+1
            //      dp[i][j] = dp[i+1][j-1] + 2
            for(int i =0;i<n;++i) dp[i][i] = 1;
            for(int i = n-1;i>=0;--i) {
                for(int j = i+1;j<n;++j) {
                    if(s[i] == s[j]) {
                        if(i+1 == j) {
                            dp[i][j] = 2;
                        }else if(i<j+1) {
                            dp[i][j] = dp[i+1][j-1] + 2;
                        }
                    }else {
                        dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
                    }
                }
            }
            return dp[0][n-1];
        }
    }
}